
import sys
sys.path.append('..')
from functools import reduce
from bisect import bisect_left
import utils.code_ana as ucana
import random
import string


def generate_random_string(length):
    letters = string.ascii_letters + string.digits + string.punctuation
    return ''.join(random.choice(letters) for i in range(length))


# 最长回文子串, 输入: "babad"，输出: "bab"。 输入：PATZJUJZTACCBCC，输出：ATZJUJZTA
longest_palindrome = lambda s: max((s[i:j] for i in range(len(s)) for j in range(i+1, len(s)+1) if s[i:j] == s[i:j][::-1]), key=len)

# 测试代码
print(longest_palindrome("babad"))  # 输出应为 "bab" 或 "aba"
print(longest_palindrome("PATZJUJZTACCBCC"))  # 输出应为 "ATZJUJZTA"

print('*'*100+'比较算法')

@ucana.performance_analysis
def longest_palindrome1(s):
    max_palindrome = ''             # 初始化最长回文子串为空字符串
    for i in range(len(s)):         # 遍历字符串的每一个子串
        for j in range(i+1, len(s) + 1):
            current_substring = s[i:j]                              # 提取当前子串
            if current_substring == current_substring[::-1]:        # 检查是否为回文
                if len(current_substring) > len(max_palindrome):    # 更新最长回文子串
                    max_palindrome = current_substring
    
    return max_palindrome
# 测试代码



# 中心扩展算法
@ucana.performance_analysis
def longest_palindrome2(s):
    def expand_around_center(left, right, s):
        while left >= 0 and right < len(s) and s[left] == s[right]:
            left -= 1
            right += 1
        return s[left + 1:right]
    
    max_palindrome = ""
    for i in range(len(s)):
        # 以字符为中心扩展
        palindrome1 = expand_around_center(i, i, s)
        # 以字符间隙为中心扩展
        palindrome2 = expand_around_center(i, i + 1, s)
        
        # 取较长的回文子串
        if len(palindrome1) > len(max_palindrome):
            max_palindrome = palindrome1
        if len(palindrome2) > len(max_palindrome):
            max_palindrome = palindrome2
    
    return max_palindrome


# Manacher's Algorithm 
@ucana.performance_analysis
def longest_palindrome3(s):
    # 预处理字符串，例如：'abc' 变为 '#a#b#c#'
    t = '#'.join(s)
    t = '#' + t + '#'
    
    P = [0] * len(t)

    # C（Center）是当前找到的回文子串的中心位置。
    # R（Right Boundary）是当前找到的回文子串的最右边界。
    C, R = 0, 0

    for i in range(len(t)):
        # 计算对称点
        mirror = 2 * C - i
        
        # 初始化 P[i]
        if i < R:
            P[i] = min(R - i, P[mirror])
        
        # 中心扩展
        a, b = i + (1 + P[i]), i - (1 + P[i])
        while a < len(t) and b >= 0 and t[a] == t[b]:
            P[i] += 1
            a += 1
            b -= 1
        
        # 更新 C 和 R
        if i + P[i] > R:
            C, R = i, i + P[i]
    
    # 提取最长回文子串
    max_len, center = max((n, i) for i, n in enumerate(P))
    return t[center - max_len:center + max_len + 1].replace('#', '')





# 测试代码
random_string = generate_random_string(100000000)
# random_string = "PATZJUJZTACCBCC"
# print("Random string:", random_string)

# longest_palindrome1(random_string)

res = longest_palindrome2(random_string)
print(len(res))
longest_palindrome3(random_string)
